package algorithm.heap;

import algorithm.QuickSort;
import util.BaseUtil;
import util.GsonUtil;

import java.util.Arrays;

/**
 *
 * 类似leetcode的题, 只不过是求前k大的全部合第k大而已。
 * @see algorithm.heap,KthLargestElementInArray
 *
 * leetcode : https://leetcode.com/problems/kth-largest-element-in-an-array/description/
 * Difficulty : Medium
 *
 *
 * TopK 问题  堆排序 小顶堆 大顶堆
 *
 * 给定一个大量的数据，比如百万或者千万级别。但是内存只给很小的部分。
 * 求这么多数里，最大的K个 or 最小的K 个的数。
 *
 * 思路：构建大顶堆 Or 小顶堆，然后逐个遍历数组，与堆顶元素比较，并入堆。
 * 难点：堆的构建子元素上浮，元素入堆顶元素的下沉。
 *
 * 创建顶堆时，逐个遍历子节点，将子节点上浮
 * 插入顶堆时，将值与子节点比较，逐个下沉。
 *
 *
 * 参考:
 * TopK问题的讨论，三种方法的实现:
 * https://blog.csdn.net/samjustin1/article/details/52704323
 *
 * BFPRT算法（基于快读排序）
 * https://segmentfault.com/a/1190000008322873
 * 
 * @Author Antony
 * @Since 2018/6/20 15:55
 */
public class TopKSolution {

    public static void main(String[] args) {
        int[] arr = BaseUtil.randomIntArray(20, 200, true);
        int[] arrCopy = Arrays.copyOf(arr,20);
        System.out.println("原数列：" + GsonUtil.toJson(arr));

        QuickSort.quickSort(arrCopy);
        System.out.println("排序后：" + GsonUtil.toJson(arrCopy));

        int k = 10;
//        topK(arr, k);
        bottomK(arr, k);

    }


    /**
     * TopK 最大的K个数。使用小顶堆
     * @param arr
     * @param k
     */
    private static void topK(int[] arr, int k){
        int[] arr_k = Arrays.copyOf(arr, k);
        System.out.println("前"+k+"个："+ GsonUtil.toJson(arr_k));

        int[] heap = createMinTopHeap(arr, k);
        System.out.println("构建小顶堆："+ GsonUtil.toJson(heap));

        for(int i=k; i<arr.length; i++){
            if(arr[i] > heap[0]){
                minTopInsert(heap, arr[i]);
            }
        }

        System.out.println("小顶堆结果：" + GsonUtil.toJson(heap));
        QuickSort.quickSort(heap);
        System.out.println("结果排序后：" + GsonUtil.toJson(heap));
    }


    private static void bottomK(int[] arr, int k){
        int[] arr_k = Arrays.copyOf(arr, k);
        System.out.println("前"+k+"个："+ GsonUtil.toJson(arr_k));

        int[] heap = createMaxTopHeap(arr, k);
        System.out.println("构建大顶堆："+ GsonUtil.toJson(heap));

        for(int i=k; i<arr.length; i++){
            if(arr[i] < heap[0]){
                maxTopInsert(heap, arr[i]);
            }
        }

        System.out.println("大顶堆结果：" + GsonUtil.toJson(heap));
        QuickSort.quickSort(heap);
        System.out.println("结果排序后：" + GsonUtil.toJson(heap));

    }

    /**
     * 创建k个节点的小顶堆
     * @param a
     * @param k
     * @return
     */
    static int[] createMinTopHeap(int a[], int k){
        int result[] = new int[k];

        // 从中取出k个元素
        for(int i=0; i<k; i++){
            result[i] = a[i];
        }

        for(int i=1; i<k; i++){
            int childIndex = i;
            int parentIndex = (i-1)/2;
            int temp = a[i];    // 临时保存当前child节点的值
            while(parentIndex >= 0 && childIndex != 0 && result[parentIndex] > temp){
                result[childIndex] = result[parentIndex];
                childIndex = parentIndex;
                parentIndex = (parentIndex - 1) / 2;
            }

            result[childIndex] = temp;
        }
        return result;
    }


    /**
     * 构造大顶堆
     * @param arr
     * @param k
     * @return
     */
    static int[] createMaxTopHeap(int[] arr, int k){
        int[] result = new int[k];
        for(int i=0; i<k; i++){
            result[i] = arr[i];
        }

        for(int i=1; i<k; i++){
            int childIndex = i;
            int parentIndex = (i-1)/2; //向下取整
            int temp = result[i];
            while(parentIndex>=0 && childIndex !=0 && result[parentIndex] < temp){
                result[childIndex] = result[parentIndex];
                childIndex = parentIndex;
                parentIndex = (parentIndex-1) / 2;
            }
            result[childIndex] = temp;
        }

        return result;
    }


    static void minTopInsert(int[] heap, int value){
        heap[0] = value;
        int parent = 0;
        int lchild, rchild, minIndex;
        while(parent < heap.length){
            lchild = 2*parent + 1;
            rchild = 2*parent + 2;
            minIndex = parent;
            if(lchild<heap.length && heap[minIndex] > heap[lchild]){
                minIndex = lchild;
            }
            if(rchild<heap.length && heap[minIndex] > heap[rchild]){
                minIndex = rchild;
            }
            if(minIndex == parent){
                break;
            }else{
                int temp = heap[parent];
                heap[parent] = heap[minIndex];
                heap[minIndex] = temp;
                parent = minIndex;
            }
        }
    }

    static void maxTopInsert(int[] heap, int value){
        heap[0] = value;    //第一步先替换堆顶节点
        int parentIndex = 0;
        while (parentIndex < heap.length) {
            int lchildIndex = 2*parentIndex + 1;    //左子节点
            int rchildIndex = 2*parentIndex + 2;    //右子节点
            int maxIndex = parentIndex;             //当前的最大节点Index

            if(lchildIndex < heap.length && heap[maxIndex] < heap[lchildIndex]){
                maxIndex = lchildIndex;
            }
            if(rchildIndex < heap.length && heap[maxIndex] < heap[rchildIndex]){
                maxIndex = rchildIndex;
            }

            if(maxIndex == parentIndex){
                break;
            }else{
                // 把parent 和 maxIndex 数据交换
                int temp = heap[parentIndex];
                heap[parentIndex] = heap[maxIndex];
                heap[maxIndex] = temp;
                parentIndex = maxIndex;
            }
        }

    }


}
